/*
 * @lc app=leetcode.cn id=117 lang=typescript
 *
 * [117] 填充每个节点的下一个右侧节点指针 II
 */

// @lc code=start
/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     left: Node | null
 *     right: Node | null
 *     next: Node | null
 *     constructor(val?: number, left?: Node, right?: Node, next?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function connect(root: Node | null): Node | null {
  // 利用本层去处理下一层的next
  const layerConnect = (node: Node | null): Node | null => {
    // 当前层头一个节点指针
    let p = node;
    // 记录当前层上一个访问的节点指针
    let pre = null;
    // 当前层头一个节点
    let head = null;

    while (p) {
      if (p.left) {
        if (pre) pre.next = p.left;
        pre = p.left;
      }
      if (head === null) head = pre;
      if (p.right) {
        if (pre) pre.next = p.right;
        pre = p.right;
      }
      if (head === null) head = pre;
      p = p.next;
    }

    return head;
  };

  let p: Node = root;
  // 每次返回下一层的完成next指针的头节点
  while (p) {
    p = layerConnect(p);
  }
  return root;
}
// @lc code=end
